package LeetCodeHot100TopInterview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Q056_MergeInterval {

    //合并区间
    //贪心 尝试 不证明 按照左端点排序,后一个左端点与上一个右端点比较,成则更新右边界
    //==> 最后只返回两个边界
    public int[][] merge(int[][] intervals) {

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            //二维数组内的元素
            public int compare(int[] o1, int[] o2) {
                //按第一个端点进行比较 默认升序
                return o1[0] - o2[0];
            }
        });

        List<int[]> merge = new ArrayList<>();
        //双指针
        int L = 0;
        int R = 0;
        for (int i = 0; i < intervals.length; i++) {
            L = intervals[i][0];
            R = intervals[i][1];
            if (merge.isEmpty() || L > merge.get(merge.size() - 1)[1]){
                merge.add(intervals[i]);
            }else {
                // L < R(last)
                //更新最后一个区间
                merge.get(merge.size() - 1)[1] = Math.max(merge.get(merge.size() - 1)[1], R);
            }
        }
        int[][] ans = new int[merge.size()][2];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = merge.get(i);
        }

        return ans;
    }

}
